package leetcode.binarysearch;

import java.util.Arrays;

//二分查找
//34. 在排序数组中查找元素的第一个和最后一个位置---个人感觉双指针比二分好写
//33. 搜索旋转排序数组
//74. 搜索二维矩阵
public class SearchRange {

    public static void main(String[] args) {
        int[] data1 = {5, 7, 7, 8, 8, 10};
//        int[] data1 = {1};
        int[] data2 = {4, 5, 6, 7, 0, 1, 2};
//        int[] ints = searchRange12(data1, 8);
//        System.out.println(Arrays.toString(ints));
//        System.out.println(search22(data2, 0));
        int[] ints = new SearchRange().searchRangePro(data1, 8);
        System.out.println(Arrays.toString(ints));
    }

    //双指针
    public static int[] searchRange(int[] nums, int target) {

        int n = nums.length;
        int[] res = new int[2];
        int p = 0;
        int q = n - 1;

        while (p <= q && nums[p] != target) {
            p++;
        }
        res[0] = p;
        while (p <= q && nums[q] != target) {
            q--;

        }
        res[1] = q;
        if (p > q) {
            res[0] = res[1] = -1;
        }
        return res;
    }

    public static int[] searchRange12(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        int[] res = new int[]{-1, -1};
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                res[0] = res[1] = mid;
                while (left < mid) {
                    if (nums[left] == target) {
                        res[0] = left;
                        break;
                    }
                    left++;
                }
                while (right > mid) {
                    if (nums[right] == target) {
                        res[1] = right;
                        break;
                    }
                    right--;
                }
                break;
            }
        }
        return res;
    }

    //暴力搜索
    public static int search(int[] nums, int target) {
        int i;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        if (i == nums.length) {
            return -1;
        }
        return -1;
    }

    //二分
    public  static int search22(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[left] <= nums[mid]) {//说明前面有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            if (nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }


    //暴力搜索
    public static boolean searchMatrix(int[][] matrix, int target) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    //二分
    public static boolean searchMatrix32(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            int x = matrix[mid / n][mid % n];
            if (x == target) {
                return true;
            } else if (target > x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

    //二刷
    //使用双指针
    public int[] searchRangePro(int[] nums, int target) {
        int p = 0;
        int q = nums.length - 1;
        int i = 0, j = 0;
        while (p <= q && nums[p] != target) {
            p++;
        }
        i = p;
        while (p <= q && nums[q] != target) {
            q--;
        }
        j = q;
        if (i > j) {
            return new int[]{-1, -1};
        }
        return new int[]{i, j};
    }
}
